package hot;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author lakersUp
 * @Classname   组合总数
 * @Description     回溯,去重
 * @Date 2022/3/9 16:20
 * @Version 1.0
 */
public class Hot39combinationSum {
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates,target,new ArrayList<Integer>(),0,0);
        return res;
    }

    private void dfs(int[] candidates, int target, List<Integer> list, int sum,int index) {
        if(sum==target){
            res.add(new ArrayList<>(list));
            return;
        }
        if(sum>target){
            return;
        }
        for(int i=index;i<candidates.length;i++){
            //剪枝, 加快速度
            if(target-sum<candidates[i]){
                break;
            }

//            if(index>=i){
                sum+=candidates[i];
                list.add(candidates[i]);
                dfs(candidates, target, list, sum,i);
                list.remove(list.size()-1);
                sum-=candidates[i];
                //      }
        }
    }
}
